Search for: All records

We present a series of nine Computational Geometry Concept Videos, available on Youtube. The videos are aimed at a general audience and introduce concepts ranging from closest and farthest pairs to data structures for range searching and for point location. The video series grew out of the development of an online graduate course on computational geometry, and the beginning portions of the videos are used in the course to motivate the concept and to tie it to a "real" problem in New Orleans. Thus our videos serve a dual purpose of outreach and education. 

In this article, we study a wide range of variants for computing the (discrete and continuous) Fréchet distance between uncertain curves. An uncertain curve is a sequence of uncertainty regions, where each region is a disk, a line segment, or a set of points. A realisation of a curve is a polyline connecting one point from each region. Given an uncertain curve and a second (certain or uncertain) curve, we seek to compute the lower and upper bound Fréchet distance, which are the minimum and maximum Fréchet distance for any realisations of the curves. We prove that both problems are NP-hard for the Fréchet distance in several uncertainty models, and that the upper bound problem remains hard for the discrete Fréchet distance. In contrast, the lower bound (discrete [ 5 ] and continuous) Fréchet distance can be computed in polynomial time in some models. Furthermore, we show that computing the expected (discrete and continuous) Fréchet distance is #P-hard in some models. On the positive side, we present an FPTAS in constant dimension for the lower bound problem when Δ/δ is polynomially bounded, where δ is the Fréchet distance and Δ bounds the diameter of the regions. We also show a near-linear-time 3-approximation for the decision problem on roughly δ-separated convex regions. Finally, we study the setting with Sakoe–Chiba time bands, where we restrict the alignment between the curves, and give polynomial-time algorithms for the upper bound and expected discrete and continuous Fréchet distance for uncertainty modelled as point sets. 

In Lombardi drawings of graphs, edges are represented as circular arcs and the edges incident on vertices have perfect angular resolution. It is known that not every planar graph has a planar Lombardi drawing. We give an example of a planar 3-tree that has no planar Lombardi drawing and we show that all outerpaths do have a planar Lombardi drawing. Further, we show that there are graphs that do not even have any Lombardi drawing at all. With this in mind, we generalize the notion of Lombardi drawings to that of (smooth) k-Lombardi drawings, in which each edge may be drawn as a (differentiable) sequence of k circular arcs; we show that every graph has a smooth 2-Lombardi drawing and every planar graph has a smooth planar 3-Lombardi drawing. We further investigate related topics connecting planarity and Lombardi drawings.